Results: Algorithm 3
2024-11-07
Tests
Levels tested: Extreme + x for x in [0,25,50,100,all] all implies L = Y, ie not defined by Yse.
We expect that q_stats increase in the number of subproblems (when Ys_is_Gs is removed).
## # A tibble: 9 × 5
## # Groups: m [3]
## m subset_global_method q_mean q_unknown_mean instance_count
## <dbl> <chr> <dbl> <dbl> <int>
## 1 2 m|m 0.343 0.0882 288
## 2 2 ul|u 0.448 0.147 144
## 3 2 u|u 0.164 0.0632 72
## 4 3 m|m 0.349 0.0747 1152
## 5 3 ul|u 0.616 0.214 384
## 6 3 u|u 0.164 0.0474 384
## 7 4 m|m 0.333 0.0726 2016
## 8 4 ul|u 0.581 0.206 1124
## 9 4 u|u 0.157 0.0339 1260Suprisingly we find that \(q^M\) decreases in the number of subproblems? (Maybe because only a subset of all instances have been run? instances with many known vectors not run for m=4).
Effects of lower bound:
We here consider the effect of assumptions on the lower bound set. We compare the cases where all vectors of the
We consider only the \(\bar q^s\) values where the lower bound used in ALG3_pair. In the above table
We now compare the q_stats for different levels of known vectors \(\frac{|\hat Y^s|}{|Y^s|}\). To limit the number of plots we split the ration of known vectors if other subproblems into intervals of 25%.
Check the size of RGS relative to MGS
\[ \frac{|\hat G^s|}{|G^s|} \]
Now we consider the number of removed vectors relative to the subproblem size:
Here we see a trend that a higher proportion of redundant vectors are identified/removed when more vectors are known.
Instance validation
Total subproblems: 10600
Total instances solved: 3154.
Total instances: 9432
TODO (check all instances are solved).
## # A tibble: 5 × 5
## # Groups: m, subset_global_method, partial_levels [1]
## m subset_global_method partial_levels other_partial_levels count
## <dbl> <chr> <dbl> <dbl> <int>
## 1 2 ul|u 0 0 4
## 2 2 ul|u 0 25 4
## 3 2 ul|u 0 50 4
## 4 2 ul|u 0 75 4
## 5 2 ul|u 0 100 4Section text
For reference: ALG3_Pair
How many redundant vectors can be identified using [ALG3_pair]
When solving MSPs,information from other subproblems, along with theorem~X, can be used to decrease the search area for minimum generator vectors of each subproblem. ALG3_pair utilizes subproblem information, specifically bound sets of subproblems, to identify redundant vectors within subproblems. The results of ALG3_pair will serve as an indicator, of how many vectors that can be removed from the search areas of subproblems using theorem~X. As in the previous section, \(G\) will denote the unique minimum generator set for each instance, while \(\hat G\) will denote the reduced generator set returned by ALG3_pair.
We expect to show that the number of identified redundant vectors increases with the ‘quality’ of the provided lower and upper bound sets of the subproblem. To test this hypothesis, we will define various lower and upper bound sets for each instance used in subsection~[MGS study subsection].
For each subproblem, we will randomly generate subsets of nondominated subproblem vectors \(\hat Y^s \subseteq Y^s_N\), and use these to define bound sets. Motivated by the fact that all supported extreme vectors of subproblems must be part of any generator set, and hence must be computed, we generate bound sets which always assume that these vectors are known in the subproblems. We will compare two types of lower bound sets: \(L^s = conv(Y_{se}^s)_N\) and \(L^s = Y^s_N\). Given a subset \(\hat{Y}^s \subseteq Y^s_N\) we will define an upper bound set using the local nadir vectors of \(\hat Y^s\). In Plot~[Visualization plot], we show an example of each type of lower bound set.
TODO create visualization with the two subplots.
Given some \(\lambda^s \in [0,1]\), we will define a subset \(\hat Y^s \subseteq Y^s\) of partial level \(\lambda^s\) as a random subset of \(Y^s\) that contains all extreme supported vectors \(Y^s_{se}\) along with \(\lambda^s\) (proportion) of the remaining vectors of \(Y^s\). Examples of partial sets and the nadir point induced upper bounds for \(\lambda^1 = 25\) and \(\lambda^1 = 75\) can be seen in Plot~[Visualization plot] . In our experiments, we create instances for different levels of \(\lambda^s \in \{0, 25\%, 50\%, 75\%, 100\%\}\) for all subproblems.
For each subproblem, we define the measure \(\bar q^s = \frac{|Y^s|- |\hat G^s|}{|Y^s|-|G^s|}\) as the proportion of redundant vectors in \(Y^s \setminus G^s\) identified by the algorithm [alg3_pair]. The measure is undefined when no redundant vectors exist \((Y^s = G^s)\), hence any such subproblem will not be included in the following when reporting aggregated results, unless explicitly stated.
For each subproblem \(s\) we seek to investigate the effect of \(\lambda^s\) on \(q^s\) and as well as the effect of the partial levels \(\lambda^{s'}\) for \(s' \neq s\). To simplify the analysis we assume all other subsets have the same partial level denoted \(\lambda^{-s}\).
We stress that $ ^s $, does not correspond to the proportion of known vectors i.e, \(\lambda^s \neq \frac{|\hat Y^s|}{Y^s}\), but instead \(\lambda^s\) indicates the proportion of non-extreme vectors of the subproblem. In Table~below, we present the actual relative size of the known sets for each method-subproblem, aggregated over all subproblem cardinalities \((|Y^s|)\) and subproblem count \((m)\). The table includes subproblems where no redundant vectors exists. Table~[below] shows how the relative size of the partial sets \(\frac{|\hat Y^s|}{|Y^s|}\) ranging from [0.02-0.09, 1] for subsets generated with u and m methods, while ranging from [0.72, 1] for subproblems generated with method l.
TODO: combine the two tables and format in LaTeX:
Table text: First part shows \(\frac{|\hat Y^s|}{|Y^s|}\) as a function of \(\lambda^s\), second part shows \(\frac{|\hat Y^s|}{|Y^s|}\) as a function of \(\lambda^{-1}\).
We will limit the analysis to instances with \(m = 2,3,4\) subproblems and \(p = 2\) objectives. An instance is solved for each combination of partial levels, m, sizes and configuration.
TODO: add a combinatorial argument to why \(m = 5\) is skipped. Use the combinatorial argument to count the total number of subproblems.
A total of 1000 out of 10600 subproblems satisfied \(Y^s = G^s\), which are skipped in the following analysis.
Aggregated results
TODO: fix group_by - first subproblem, then instance then all
Aggregated over all instances using the lower bound sets defined by the extreme supported solutions, the ranges (average) of the \(q^s\) values for each configuration were \(q^{m|m} \in [0.0, 73.7]\ (19.9\%)\), \(q^{ul|u} \in [0.0, 82.5]\ (45.0\%)\) and \(q^{u|u} \in [0.0, 0.0]\ (0.0\%)\). We immediately see that no redundant vectors were identified in the u|u subproblems. For these subsets, the upper bound consists often of only the nadir points, which is a bad representation of \(Y_N^s\) resulting in low \(\bar q^s\) values. For the remaining configurations ul|u and m|m the algorithm managed to identify a significant number of redundant vectors, resulting in large \(q^s\) values.
Averaging over all subproblems, for each partial levels \(\lambda^s\), we get the \(q^s\) values 7.7, 16.1, 22.9, 27.7 and 31.2 percent for 0, 25, 50, 75 and 100. Overall, we see a clear improvement when increasing the known partial level.
To further investigate the results, the \(q^s\) values relative to partial levels \(\lambda^s\) (x-axis), \(\lambda^{-s}\) (columns), and subproblem count \(m\) (rows), are presented in Plot~A, with a color for each configuration.
Having filtered out the cases where \(Y^s = G^s\), and considering only lower bound sets defined by extreme supported vectors, plot~A contains points for each subproblem \(q^s\) value, with a trend line defined by the average for each partial level \(\lambda^s\).
Firstly, note that for fixed \(\lambda^{-s}\) (column), \(m\) (row), and configuration (color), the average \(q^s\) values increase monotonically in \(\lambda^s\) for the subproblems m|m and ul|u. We again note that for u|u instances, the algorithm failed to identify any redundant vectors, as previously seen in the aggregate statistics, which we explained by the low-quality lower bound set. In the sequel, we will see how this changes when the stronger lower bound sets are used.
Each such line increases with \(\lambda^s\), but the derivative of \(q^s\) with respect to \(\lambda^s\) decreases, indicating diminishing returns in identifying redundant vectors as the upper bound quality increases.
In summary, more information of subproblems results in more identified redundant vectors, but the effect is decreasing in the amount of vectors known.
To see the effect of changing \(\lambda^{-s}\) for fixed configuration (color) and \(\lambda^s\) value (x-axis), observe that the average \(q^s\) values increase in \(\lambda^{-s}\) (moving right between subplots). We see a consistent increasing trend for m|m and a small but monotone increase for ul|u. The small effect on \(q^s\) when increasing \(\lambda^{-s}\) in the ul|u case can be explained by the fact that a large increase in \(\lambda^{-s}\) values corresponds to a small increase in the relative known vectors \(\frac{|\hat Y^s|}{|Y^s|}\) as reported in the table~[above]. We therefore have the consistent interpretation showing that \(q^s\) increases in the quality of the upper bound sets.
Looking at Plot~A for fixed partial levels \(\lambda^s\), \(\lambda^{-s}\) and configuration (color), we see the effects of \(m\) on \(q^s\) by moving vertically between subplots. We hypothesize that \(q^s\) increase in \(m\) as fewer vectors are needed when increasing \(m\). In particular, we expect \(|G^s|\) to decrease faster than \(|\hat G^s|\) as the ‘scope’ of finding MGS is more extensive than the pairwise method for identifying redundant vectors. Consider the example where \(m=3\), and a subproblem vector in Subset 1 is needed in the MS \(Y^{12} = (Y^1 + Y^2)_N\), but redundant when considering the global MS: \(Y_n = (Y^{12} + Y^3)_N\) . Such a vector, however, would not necessarily be identified by ALG_3 which only checks pairwise for dominance.
For m|m, we see a clear tendency that \(q^s\) decreases as a function of \(m\), implying that the MGS decrease more than the RGS returned by the algorithm. Surprisingly, we do not see this trend in the ul|u case, which is likely a result of the generation method where not all subproblems are created using the same generation method. For \(m=2\) has methods \(ull\) and \(m=4\) has \(uull\). As such, the effect of \(m\) is inconclusive.
Lower bound sets
We will now consider the effect of the lower bound set quality on \(q^s\) for fixed \(\lambda^{-s} = 100\). Both types of lower bound sets \(L^s = conv(Y^s_{se})_N\) and \(L^s = Y^s_N\) are visualized in subplot a and b, respectively, in Figure~[Visual]. We summarise the results in Plot ALB. For fixed configuration (color), \(\lambda^{s}\) (x-axis), we see a large effect on the \(q^s\) values when using the tighter lower bound set (moving right). Unlike the previous plot~[A ref], we see a large improvement in \(q^s\) values for u|u subproblems when using the stronger lower bound sets. The subplots in the right column also show how \(q^s\) is increasing in \(\lambda^s\) for u|u subproblems as previously seen for the cases m|m and ul|u. We also find a significant improvement in \(q^s\) values for the ul|u and m|m cases using the stronger lower bound sets.
In our experiments, we only consider two lower bound sets with rather extreme quality differences for some subproblems. One could also consider lower bound sets based on the extreme supported solutions and remove known empty search regions by adding local nadir vectors, i.e, a hybrid lower bound set.
To summarise, the empirical study on the effectiveness of ALG3_pair, we observe that a significant number of redundant vectors are identified in most subproblems when good upper and lower bound sets are known. In some cases, a smoll inprovement in an upper bound leads to substantial improvement in the ALG3_pair performance.
This suggests that using generator upper bound sets in ALG3_pair can effectively avoid generating redundant subproblem solutions when solving subproblems, especially when good bound sets are available.
end of text
TODO: del op for m, tjek om der er samme stigning for all m ✅ Tabel er nu fordelt på m.
In the table [ref], we summarize results for \(m=2, p=2\) where \(\hat Y^2 = Yn^2\), comparing the effects of the different lower bounds \(L^s = Y_N\) and \(L^s = conv(Y^s_N)\). This shows that the improved lower bound set obtained using the assumption, significantly improves the number of redundant vectors that can be identified by [ref alg3_pair].
Plot A version
u|u er konstant q^s = 0 for alle partielle niveauer (Når L^(-s) er fra de 2 ekstreme punkter. Dette skyldes at lower bound der bruges til at fjerne punkter er ringe. I modsætning hertil fås høje q^s værdier for u subsets i instanserne ul|u. Nævn kun for i denne sektion. Der opnås også højrere q^s værdier når L^(-s) = Yn^(-s). Igen bedre LB => bedre q^s Main point: Better known sets => Better bound sets => better q^s values => more redundant vectors identified => More redundant can be avoided by using RGS bound sets when solving subproblems. In some cases a small improvement of an upper bound on Yn^s can give a much better improvement on the RGS bound of G^s.
Plot B version
other plots (relative known points)
Same plot as above, but now we consider the relative size of the known subsets \(\frac{|\hat Y^s|}{Y_N^s}\) instead of the partial level (\(\lambda^s\)). Again we see that \(\bar q^s\) increases in both the number of known vectors.
other plots (removed points)
In the following, we plot the proportion of vectors removed from subproblems (\(\bar t^s\)).
(Maybe add the above lines in the first plot as dashed lines?)
In the plot [above], we plot the number of redundant vectors removed from each subproblem relative to the subproblem size. Here it is clear that no redundant vectors are found in the cases \(ul|l\) and \(u|u\).
Other plots (removed unknown vectors)
Compare removed \(Y^s \setminus \hat G^s\) and removed unknown \(Y^s \setminus \hat G^s \setminus \hat Y^s\).
Same plots as above, but statistics for unknown \((U)\) vectors. \[\bar q_U^s = \frac{|Y^s \setminus \hat G^s \setminus \hat Y^s|}{|Y^s|-|G^s|}\] \[\bar t_U^s = \frac{|Y^s \setminus \hat G^s \setminus \hat Y^s|}{|Y^s|}\]
Some 3d plots
other plots (q as function of known_relative grouped)
average by
(dashed lines shows \(removed\_unkown / |Y_N^s|\))
The relative plot from above:
